#
# @lc app=leetcode.cn id=78 lang=python3
#
# [78] 子集
#

# @lc code=start


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        求子集：
        填空 [] * len(nums)
        每一个数可选可不选
        """
        # 结果集
        self.res = []
        self._backtrack([], 0, nums)
        return self.res

    def _backtrack(self, track, index, nums):
        """
        track: 路径记录
        index: 遍历到的位置
        """
        # 出口
        if index == len(nums):
            self.res.append(track)
            return

        # 选择该层
        # track.append(nums[index])     如果直接加 就改变了下一层track
        self._backtrack(track+[nums[index]], index + 1, nums)
        # 不选该层
        self._backtrack(track, index + 1, nums)
        # @lc code=end
